#include <iostream>

// 斐波那契数列的递归和循环写法
int FibonacciRecursive(int num) {
  if (num <= 0) {
    return 0;
  }
  if (num == 1) {
    return 1;
  }
  return FibonacciRecursive(num - 1) + FibonacciRecursive(num - 2);
}

int FibonacciIterative(int num) {
  int ret[] = {0, 1};
  if (num < 0) {
    return 0;
  }
  if (num < 2) {
    return ret[num];
  }

  int result = 0;
  int revert_one = 1;
  int revert_two = 0;
  for (int i = 2; i <= num; ++i) {
    result = revert_one + revert_two;
    revert_two = revert_one;
    revert_one = result;
  }
  return result;
}

int main() {
  int num = 40;
  int ret_recursive = FibonacciRecursive(num);
  int ret_iterative = FibonacciIterative(num);
  std::cout << "FibonacciRecursive 10: " << ret_recursive << std::endl;
  std::cout << "FibonacciIterative 10: " << ret_iterative << std::endl;
  return 0;
}
